Custom integrated circuits are often designed to implement certain digital signal processing (DSP) applications to achieve the required performance. This is especially true with DSP applications requiring parallel architectures which perform computations in one clock cycle. The designer typically implements the DSP algorithm first in software, which provides a test-bed for the algorithm. Once the DSP algorithm is sufficiently tested and debugged in software, the algorithm is implemented again in hardware to reflect the software implementation. However, due to the different tools and basic building blocks available in hardware design, the resultant hardware implementation may function differently from the software prototype, or fail altogether. Therefore, a translator is needed which can derive a hardware implementation directly from a software implementation, so that errors from the reimplementation process can be eliminated.
One identified way to achieve the software to hardware translation is to first translate the software algorithm into a data flow graph from which a hardware circuit can be derived. One technique of translation is symbolic evaluation, which is related to the compilation technique of partial evaluation. Partial evaluation evaluates portions of the program with known inputs and the portions of the program with unspecified inputs are evaluated only at run time. Symbolic evaluation, on the other hand, treats and computes all inputs symbolically. Therefore, if the program has no data dependencies, it can be evaluated fully. However, few algorithms are data independent. For example, an algorithm has data-dependent control flow if the condition of an IF statement or the bound on a FOR loop is dependent on some input data.
Conventional methods of symbolic evaluation cannot satisfactorily handle algorithms with data-dependent control flow. Accordingly, a need has arisen for a technique for symbolic evaluation of algorithms with data-dependent control flow. Such technique not only would benefit the application thereof to DSP hardware design, but also to optimization of programs by compilers, and to those applications where parallelism needs to be exploited.